home *** CD-ROM | disk | FTP | other *** search
Text File | 1988-12-01 | 42.9 KB | 1,344 lines |
-
- IEN 196 11 September 1981
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- ISSUES INVOLVING NON-ROUTING GATEWAYS
-
-
-
- B. Bowman & P. Cook
-
-
- Ford Aerospace & Communications Corporation
-
- Colorado Springs, Colorado
-
- (303-471-9110)
-
-
- IEN # 196
-
-
-
- September 11, 1981
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- IEN 196 11 September 1981
-
-
- INTRODUCTION
-
- This note presents some proposed modifications to the gateway
- routing algorithm and the protocol for exchanging routing
- information described in IEN #109, "How To Build A Gateway". The
- described algorithm modifications were defined as a result of
- problems encountered in the implementation of the gateway to
- gateway control protocol specified in IEN # 109. The problems
- encountered in implementing the algorithm involve the mechanisms
- for incorporating non-routing gateways in the catenet.
- Therefore, this discussion focuses on modifications designed to
- facilitate use of non-routing gateways in concert with routing
- gateways in the catenet.
-
- As indicated above, the issues discussed resulted from our
- implementation of the IEN # 109 algorithm. Some initial
- implementation questions concerning interpretation of the rules
- for assembling routing updates from non-routing gateways led to
- our analysis of the design of this routing strategy. From
- routing strategy design issues, our study progressed to questions
- regarding the intended/optimal role of non-routing gateways in
- the catenet.
-
- As a result, this note presents specific modifications to IEN #
- 109 necessary for successful implementation and also includes
- discussion of the broader issues of the role of the non-routing
- gateway in the catenet.
-
- Finally, we propose a modification to the routing information
- exchanged in the IEN # 109 algorithm, which we believe has
- significant advantages in reducing the logical complexity of the
- algorithm and traffic between gateways. Although we have looked
- at design approaches of other authors in this field, we have not
- done an exhaustive search to determine the "novelty" of our
- approach. We would also like to stress that our goal was not to
- design a new routing algorithm but simply to implement the IEN #
- 109 algorithm. In a very real sense, it can be said that we
- backed into these routing design issues as a natural consequence
- to our implementation efforts.
-
- I. Non-Routing Gateways
-
- It should be noted that any solution must be based on an
- understanding regarding the intended role of the non-routing
- gateway in the catenet. Unambiguous rules for incorporating
- non-routing gateways in the routing scheme can only be specified
- when the intended role is clearly defined. An optimal solution,
- then, would involve clarification of the role of the non-routing
- gateway followed by revision of the routing specification
- consistent with the defined role.
-
- -2-
-
-
-
- IEN 196 11 September 1981
-
-
- IEN # 109, "How to Build a Gateway", contains a section (Sect.9,
- Page 7) discussing the interface between routing gateways and
- non-routing gateways and, in particular, discussing the use of a
- non-routing gateway by a routing gateway for routing packets.
- Two areas of this section are problematic with respect to a
- successful implementation. These are, (1) initialization with
- respect to the non-routing gateway and (2) computation of the
- minimum distance vector.
-
- A. Initialization
-
- IEN # 109 gives the following instructions for initializing with
- respect to a non-routing neighbor gateway.
-
- * "For each non-routing neighbor gateway of gateway G1, compute
- the routing update that would be sent to G1 assuming that all
- gateways and network connections are operational. These routing
- updates are assembled in G1."
-
- This rule can be interpreted in one of two ways. The first is to
- assemble the non-routing gateway's routing update showing actual
- distances to each network from the non-routing gateway. Figure 1
- shows an example of this interpretation.
-
- In this example, Gateway (B) is a non-routing gateway and Gateway
- (A) is a routing gateway. Initially, G(A) assembles G(B)'s
- update as actual distances from G(B) to the 3 networks. Based on
- this initialization, G(A) assumes that it is a distance of 1 from
- Net.#1 because the non-routing gateway provides the only path to
- Net.#1. G(A) also assumes that it is directly (0) connected to
- Nets.#2 and #3. G(A) builds its initial minimum distance vector
- reflecting these distances.
-
- Assume, then, that G(A)'s link to Net.#3 goes down at some time.
- When this happens, G(A) recomputes it's minimum distance vector.
- Since G(A) is no longer connected to Net.#3, there is no path
- available unless the non-routing gateway's path is used. G(B)'s
- update indicates a distance of 1 to Net.#3. Therefore, G(A)
- assumes a path to Net.#3 of distance 2 through G(B). Of course,
- there is no path to Net.#3 but G(B) does not accept or transmit
- routing tables so any packets addressed to Net.#3 will shuttle
- indefinitely (until the IP4 time to live field is decremented to
- zero) from G(A) to G(B) to G(A), etc. When this example is
- extended to larger catenets, the shuttling problem persists and
- simply involves higher distance shuttles. Therefore, this
- interpretation of the initialization instructions is unworkable.
-
-
- -3-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 1: INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
- "ACTUAL DISTANCE" METHOD
-
-
- CATENET CONFIGURATION
-
-
-
- __________ __________ __________
- | | | | | |
- | NET #1 |----G(B)----| NET #2 |----G(A)----| NET #3 |
- |__________| |__________| |__________|
-
-
- where
- G(A) = Gateway A: Routing Gateway
- G(B) = Gateway B: Non-Routing Gateway
-
-
- G(A) DISTANCE MATRIX AFTER INITIALIZATION
-
- NETWORKS
- GATEWAYS 1 2 3
-
-
- A 1 0 0
- B 0 0 1
-
-
-
- G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
-
- NETWORKS
- GATEWAYS 1 2 3
-
-
- A 1 0 2
- B 0 0 1
-
-
-
-
-
- -4-
-
-
-
- IEN 196 11 September 1981
-
-
- The other possible interpretation of the IEN # 109 instructions
- is to assemble the non-routing gateway's update showing actual
- distances to each network from the non-routing gateway only when
- the non-routing gateway is as close to or closer to the network
- than the gateway assembling the routing update. This
- interpretation incorporates a rule from Section 7, page 7
- regarding computation of routing updates. Figure 2 shows an
- example of this interpretation.
-
- In this example, Gateway (B is a non-routing gateway and Gateways
- A and C are routing gateways. The example is presented from the
- perspective of Gateway A. Gateway B's update is initialized
- showing 0 distance to Nets.#1 and #2. A distance of 1 is shown
- to Net.#3 because Gateway B is as close to Net.#3 as is Gateway
- A. An infinite distance is shown to Net.#4 because Gateway A is
- closer to Net.#4 than Gateway B. The example shows receipt of a
- routing update from Gateway C which shows Gateway C's distances
- calculated according to the rules for preparation of a routing
- update.
-
- Gateway A calculates its minimym distance vector as 0 distance
- from Nets.#2 and #4 because they are directly connected, distance
- 1 from Net.#1 because of the path through Gateway B and distance
- 1 from Net.#3 because of the path through Gateway C.
-
- Assuming that Gateway C loses connectivity to Network #3 at some
- time, Gateway C would send Gateway A a new routing update showing
- infinite distance to Network #3. Gateway A would then
- recalculate its minimum distance vector. G(A) would assume that
- the only path to Net.#3 is through the non-routing gateway (G(B))
- and that this is a path of distance 2. This occurs because G(B)
- neither accepts nor transmits routing updates so it is unaware of
- the connectivity loss and G(A) is assembled with G(B)'s routing
- update so there is no provision for changes to this information
- in G(A). The situation is complicated by the fact that G(A),
- upon recalculation of its minimum distance vector, will transmit
- a routing update to G(C) showing the distance of 2 from G(A) to
- Network #3. G(C) will recompute its distance vector to show a
- path of distance 3 from G(C) to Network #3. Since no path
- actually exists and all 3 Gateways believe a path exists, packets
- addressed to Net.#3 will shuttle indefinitely (until the IP4 time
- to live field is decremented to zero).
-
- Thus it seems that Thus it seems that both interpretations of the
- IEN # 109 instruction for assembling the non-routing gateway's
- update present serious problems.
-
-
- -5-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 2: INITIALIZATION OF NON-ROUTING GATEWAY UPDATE
- "TAILORED UPDATE" METHOD
-
-
- CATENET CONFIGURATION
-
-
- __________
- __________ __________ | |
- | | | |----G(A)----| NET #4 |
- | NET #1 |----G(B)----| NET #2 | |__________|
- | | | | __________
- | | | | | |
- |__________| |__________|----G(C)----| NET #3 |
- |__________|
-
-
-
- where
- G(A) = Gateway A: Routing Gateway
- G(B) = Gateway B: Non-Routing Gateway
- G(C) = Gateway C: Routing Gateway
-
-
- G(A) DISTANCE MATRIX AFTER INITIALIZATION
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
-
- A 1 0 1 0
- B 0 0 1 INF
- C 1 0 0 INF
-
-
-
- G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
-
- A 1 0 2 0
- B 0 0 1 INF
- C 1 0 INF INF
-
-
-
-
- -6-
-
-
-
- IEN 196 11 September 1981
-
-
- B. Computation of the Minimum Distance Vector
-
- IEN # 109 goes on to provide the following instructions for
- calculating the minimum distance vector when non-routing gateways
- are included.
-
- * "The gateway, G(A), first computes its minimum distance
- vector using only the routing updates from neighbors that
- participate in routing. If the minimum distance to any
- network is infinity, i.e., the network is unreachable via
- any of the routing gateways, then the minimum distance to
- that network is re-computed using the routing update
- compiled for the non-routing neighbor gateway."
-
- This rule appears inefficient if we look at the example shown in
- Figure 3. In this example, Gateway B is a non-routing gateway
- and Gateways A and C are routing gateways. The example is
- presented from the perspective of Gateway A and the focus of the
- example is on the distance to Network #1.
-
- G(A) is assembled with the update of G(B) (the non-routing
- gateway) and G(B) shows a distance of 0 from Net.#1 since it is
- directly connected. In our example, G(A) has received an update
- from G(C). G(C) shows a distance of 1 to Net.#1 based on its
- path through G(B). According to the rule, G(A) has to prefer the
- route through G(C) since G(C) is a routing neighbor and G(B) is
- non-routing. Therefore, G(A) assumes a path of distance 2 to
- Net.#1 and G(A) will route to G(C) any packets addressed to
- Net.#1. On receipt of the packet addressed to Net.#1, G(C) will
- route the packet to G(B) where it will be delivered to Net.#1.
-
- This solution is not unworkable but it does cause delay and
- inefficiency by forcing an additonal transfer with respect to the
- optimal path. In a geographically dispersed network, this delay
- and additional network traffic could become significant.
-
-
- -7-
-
-
-
- IEN 196 11 September 1981
-
-
-
- FIGURE 3: COMPUTATION OF THE MINIMUM DISTANCE VECTOR
-
-
-
- CATENET CONFIGURATION
-
-
- __________
- __________ __________ | |
- | | | |----G(A)----| NET #4 |
- | NET #1 |----G(B)----| NET #2 | |__________|
- | | | | __________
- | | | | | |
- |__________| |__________|----G(C)----| NET #3 |
- |__________|
-
-
-
- where
- G(A) = Gateway A: Routing Gateway
- G(B) = Gateway B: Non-Routing Gateway
- G(C) = Gateway C: Routing Gateway
-
-
- G(A) DISTANCE MATRIX
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
-
- A 2 0 1 0
- B 0 0 1 INF
- C 1 0 0 1
-
-
-
-
- -8-
-
-
-
- IEN 196 11 September 1981
-
-
- C. Proposed Solution to Non-Routing Gateway Problems
-
- Role Clarification
-
- As indicated above, a solution to the problems in incorporation
- of non-routing gateways must address clarification of the role of
- the non-routing gateway in the catenet. Three possible roles for
- the non-routing gateway have been identified and are discussed in
- this section. In general, we see potential for non-routing
- gateways to be used to provide 1) the "only" route, 2)
- "redundant" routes or 3) "parallel" routes. Use of the
- non-routing gateway to provide "redundant" and "parallel" routes
- is discussed in Section D.
-
- Figure 4 illustrates use of the non-routing gateway to provide
- the "only" route. This role basically restricts the use of
- non-routing gateways to allow (i.e., recognize) them in the
- catenet only when the non-routing gateway provides the "only"
- connection to a network or network branches.
-
- Although other possible roles will be discussed , this particular
- role definition is the one we recommend. Using non-routing
- gateways where they provide the "only" possible route seems the
- most logical use of these gateways and also lends itself most
- easily to unambiguous rule definition. The mechanisms for
- incorporating non-routing gateways consistent with the "only"
- route role are described in the following paragraphs.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -9-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 4: NON-ROUTING GATEWAY AS "ONLY" ROUTE
-
-
- CATENET CONFIGURATION
-
-
-
- __________ __________
- | | | |
- | NET #1 |----G(R)----| NET #3 |
- |__________| |__________|
- | |
- | |
- G(R) |
- | |
- | |
- __________ |
- | | |
- | NET #2 |----G(R)----------|
- |__________|
- |
- |
- G(NR)
- |
- |
- __________
- | |
- | NET #4 |
- |__________|
- |
- |
- etc. (network branch)
-
-
-
- G(R) = Routing Gateway
- G(NR) = Non-Routing Gateway
-
-
- NOTE: In this configuration, the non-routing gateway provides
- the only connection to Network #4.
-
-
- -10-
-
-
-
-
- IEN 196 11 September 1981
-
-
- Rules for "Only" Route Role
-
- It appears that the initialization and route computation problems
- associated with non-routing neighbor gateways described above,
- could be solved by a few rule changes. The proposed new rules
- are as follows:
-
- * IEN # 109 Rule:
-
- For each non-routing neighbor gateway of gatewayG(A),
- compute the routing update that would be sent to G(A)
- assuming that all gateways and network connections are
- operational. These routing updates are assembled in G(A).
-
- New Rule:
-
- F or each non-routing neighbor gateway of gateway G(A),
- compute the routing update that would be sent to G(A)
- assuming that all gateways and network connections are
- operational. In computing these routing updates, show
- actual (non-infinite) distances to networks which are
- reachable only through the non-routing gateway. Networks
- which are reachable by a routing gateway shall be
- initialized with distance equal infinity. These routing
- updates are assembled in G(A).
-
- IEN # 109 Rule:
-
- T he gateway, G(A), first computes its minimum distance
- vector using only the routing updates from neighbors that
- participate in routing. If the minimum distance to any
- network is infinity, (i.e., the network is unreachable via
- any of the routing gateways), then the minimum distance to
- that network is re-computed using the routing update
- compiled for the non-routing neighbor gateway.
-
- New Rule:
-
- The gateway, G(A), first computes its minimum distance
- vector using all the routing updates (including updates from
- both routing and non-routing gateways).
-
- These proposed rule changes, taken together, cause non-routing
- gateways to be used only when they provide the only path to a
- network or string of networks. These rules also eliminate the
- possibility of selecting any other path (i.e., through a routing
- gateway) when a non-routing gateway provides the only path.
- Thus, non-routing gateways are used for packet routing if and
- only if they provide the only route to a destination.
-
-
-
- -11-
-
-
-
- IEN 196 11 September 1981
-
-
- Figure 5 shows how the new rules solve the problems identified in
- Examples 1, 2, and 3. In this example, Gateway B is a
- non-routing Gateway and Gateways A and C are routing gateways.
- The example is presented from the perspective of Gateway A. The
- G(A) Distance Matrix after initialization shows that the problem
- depicted in Figure 3 (computation of the minimum distance vector)
- is resolved through application of the new rules. Since the
- minimum distance vector is calculated based equally on the
- routing and non-routing gateway updates, the shortest path (and
- only path) to Network #1 is selected by both routing gateways
- (G(A) and G(C)).
-
- The G(A) Distance Matrix resulting from loss of connectivity to
- Net.#4 shows that the problem depicted in Figure 1
- (Initialization of non-routing gateway update) is resolved
- through use of the new rules. Since the assembled non-routing
- gateway update no longer shows paths to networks reachable by
- routing gateways, G(A) is able to determine that Net.#4 is now
- unreachable and does not attempt to route traffic to Net.#4
- through Gateway (B).
-
- The G(A) Distance Matrix resulting from loss of connectivity to
- Net.#3 shows that the problem depicted in Figure 2
- (Initialization of non-routing Gateway update) is also resolved
- through application of the new rules. This problem is resolved
- because the assembled non-routing gateway update no longer show
- paths to networks reachable by routing gateways. Thus, when
- Net.#3 is declared unreachable by Gateway C, G(A) determines that
- Net.#3 is unreachable by all gateways.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -12-
-
-
-
- IEN 196 11 September 1981
-
- FIGURE 5: PROPOSED SOLUTION
-
- CATENET CONFIGURATION
- __________
- __________ __________ | |
- | | | |----G(A)----| NET #4 |
- | NET #1 |----G(B)----| NET #2 | |__________|
- | | | | __________
- | | | | | |
- |__________| |__________|----G(C)----| NET #3 |
- |__________|
-
- where
-
- G(A) = Gateway A: Routing Gateway
- G(B) = Gateway B: Non-Routing Gateway
- G(C) = Gateway C: Routing Gateway
-
- G(A) DISTANCE MATRIX AFTER INITIALIZATION
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
- A 1 0 1 0
- B 0 INF INF INF
- C 1 0 0 INF
-
-
- G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#4)
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
- A 1 0 1 INF
- B 0 INF INF INF
- C 1 0 0 INF
-
-
- G(A) DISTANCE MATRIX (ASSUMING LOSS OF CONNECTIVITY TO NET.#3)
-
- NETWORKS
- GATEWAYS 1 2 3 4
-
- A 1 0 INF 0
- B 0 INF INF INF
- C 1 0 INF INF
-
-
- -13-
-
-
-
-
- IEN 196 11 September 1981
-
-
- D. Other Possible Approaches
-
- Redundant Role
-
- Restricting the use of non-routing gateways in the catenet to
- locations where they provide the only configured path and
- adoption of the corresponding rule changes is our recommended
- solution to the implementation problems we've identified. In
- reviewing IEN # 109 and it's predecessor IEN # 30, we find it
- difficult to determine the intended role of the non-routing
- gateways.
-
- Both papers indicate that non-routing gateways are to be used to
- forward traffic only when they provide the only route to a
- network. This seems to indicate that the initial intent was to
- use non-routing gateways in the role defined above (i.e. "only"
- route role). On the other hand, it's possible that the authors
- actually intended to use the non-routing gateways to provide the
- only configured path and to provide backup routes to networks
- connected by routing gateways. This role for non-routing
- gateways is what we have called the "redundant " role. Figure 6
- illustrates this use of non-routing gateways. This role is
- basically an addition to the "only" route role.
-
- Here the non-routing gateway can also be configured in parallel
- with a routing gateway but the non-routing path is only used if
- connectivity through the routing gateway is lost. Thus, the
- non-routing gateway is used as a backup for the routing gateway.
- As long as the routing gateway and its connections are
- functional, the non-routing gateway is not used to forward any
- traffic.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 749/
-
- -14-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 6: NON-ROUTING GATEWAY AS "REDUNDANT" ROUTE
-
-
-
- CATENET CONFIGURATION
-
-
-
- __________ __________
- | |----G(NR)---| |
- | NET #1 | | NET #2 |
- |__________|----G(R)----|__________|
- | |
- | |
- G(R) G(R)
- | |
- | |
- __________________________________
- | |
- | NET #3 |
- |__________________________________|
-
-
- WHERE
- G(R) = Routing Gateway
- G(NR) = Non-Routing Gateway
-
-
-
-
-
-
-
-
- -15-
-
-
-
- IEN 196 11 September 1981
-
-
-
- It seems that this second role interpretation is implementable.
- Basically, the corresponding rules would be:
-
- 1) Assemble routing update showing direct network connections
- and actual distances to networks reachable only by the
- non-routing gateway.
-
- 2) Calculate minimum distance vector using non-routing gateway
- paths only when they provide the only route.
-
- Implementing this role concept, then, involves the added
- complexity of the two stage minimum distance vector calculation
- (with bias toward routing gateway paths). While this may be the
- role anticipated by the authors of IEN # 109 and # 30, we feel
- the backup role is of little added value for the additional
- complexity involved. It seems unlikely to us that networks would
- buy a processor which was to be idle the majority of the time.
- Instead, if need existed for a backup, it seems a routing gateway
- would be a better choice and cost efficient as it could increase
- bandwidth as well as providing redundancy.
-
- Parallel Role
-
- At the other end of the spectrum, it is possible that some group
- might wish to use non-routing gateways in any configuration where
- routing gateways can be used. In this role, which we call the
- "parallel" role, non-routing gateways are used to provide
- additional (parallel) paths and thus effectively increase
- bandwidth. This role differs from the "redundant" route role in
- that non-routing gateways are used to forward traffic even when
- they do not provide the only path. It is this facility which
- allows the effective increase in real-time bandwidth.
-
- Whether this intended role is implementable is an open question.
- Obviously, it would be more complex to implement and would
- basically require a redefinition of some of the ground rules. We
- rejected this possible role application because it significantly
- reduces catenet reliability and seems to defeat the whole idea
- behind the routing algorithm function. If non-routing gateways
- are used routinely to forward traffic in parallel with routing
- gateways, connectivity changes occuring with the non-routing
- gateways are unreported and therefore the non-routing gateways
- could easily become traffic sinks.
-
-
-
-
-
-
- -16-
-
-
-
- IEN 196 11 September 1981
-
- We felt that the only possibility for using non-routing gateways
- to increase bandwidth would be to implement the role outside the
- gateway-gateway control protocol. This function could be
- implemented as a host function where there was an understanding
- between hosts on two networks that traffic would be split on some
- basis between routing and non-routing gateways. Thus, the
- decision to sacrifice catenet reliability in favor of increased
- traffic flow would be made by the parties involved without
- involving any gateway control function awareness or
- participation.
-
- II. Routing Update Calculations
-
- In the process of designing the gateway routing software IAW IEN
- # 109, we determined that a subset of the routing algorithm rules
- dictated a logically cumbersome implementation. These rules,
- from IEN # 109 are as follows:
-
- A. "The gateway reports its distance to a network to a
- neighbor only if it is as close or closer to a network than
- its neighbor." (p.7)
-
- B. "The gateway maintains a copy of the most recent routing
- updates that it sent to each of its neighbors. The gateway
- computes the new routing updates to send to each of its
- neighbors. If any of these routing updates are different
- than the preceding updates, then the gateway sends new
- routing updates to its neighbors." (p.7)
-
- Rule A calls for "tailoring" routing updates for each neighbor
- such that the transmitting gateway reports its distance relative
- to the connectivity of each recipient gateway. Thus, when a
- gateway calculates its routing update, it first calculates its
- minimum distance vector and then compares that vector to the last
- routing update from each neighbor. From this comparison, it
- creates the "tailored" routing update for each neighbor which
- reflects not only the transmitting gateway's connectivity but
- also the connectivity of each neighbor. The comparison process
- is performed as follows:
-
-
-
-
-
-
-
- -17-
-
-
-
- IEN 196 11 September 1981
-
-
- DO (For each neighbor)
-
- DO (For each network)
-
- IF (Transmitting gateway is as close or closer to
-
- the network)
-
- Report actual distance
-
- ELSE (Report infinity distance)
-
- ENDDO
-
- ENDDO
-
- Rule B requires that, having performed the calculations based on
- Rule A resulting in routing updates for each neighbor, these
- updates be compared to the updates last sent to each neighbor.
- If any of the updates are different from those last sent, all the
- updates are transmitted. If there are no changes to any neighbor
- since the last transmittal, no updates are sent. Implementation
- of this rule requires that copies of the last updates sent be
- maintained at the gateway.
-
- The basis for these rules, particularly Rule A, is prevention of
- shuttling which could occur if only one path existed to a network
- and that network became disconnected. If gateways were allowed
- to report actual distances rather than infinity, then two
- gateways could, because of their dependent or relative distance
- relationship, begin step increments of their distances to the
- disconnected network eventually approaching infinity and thus
- shuttle packets until the IP4 time to live field is decremented
- to zero.
-
- This shuttling problem is, in fact, a natural outcome of a
- routing scheme which involves the exchange of distance
- information only. Thus, the problem can be solved by the
- addition of special rules such as Rule #1 above or can be solved
- by going to a routing scheme which exchanges connectivity
- information (distance and path).
-
-
-
-
-
-
-
-
- -18-
-
-
-
- IEN 196 11 September 1981
-
-
- After studying the current solution of exchanging relative
- distance vectors, it seems that going to a routing scheme
- involving exchange of both connectivity information and distance
- provides a simpler and more efficient solution. The added
- information exchange proposed is more than offset by the
- computational simplicity and the reduction in routing update
- traffic afforded.
-
- The routing scheme proposed provides for including in routing
- updates both the actual distance vector (as opposed to the
- current tailored relative distance vector) and the routing table.
-
- Figure 7 is a configuration used as the basis for illustration of
- the updates. To see how these routing updates are constructed,
- examine the update from G3 in Figure 8 (Step 3). G3 is directly
- connected to Nets.#2 and #26, so G3 shows a distance of 0 to each
- with G3 as the "next" gateway address for routing. G3 is 1 away
- from Net.#1 and this path to Net.#1 is through G2. Similarly, G3
- is 1 away from Nets.#3 and #27 and these paths are through G5 and
- G6 respectiviely. G3 is also a distance of 1 from Net.#10.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -19-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 7: CATENET CONFIGURATION
-
-
-
- __________ __________
- | | | |
- | NET #1 | | NET #4 |
- |__________| |__________|
- | |
- | |
- G2 G4
- | |
- | |
- __________ __________
- | | | |
- | NET #26 |-----G1----| NET #10 |
- |__________|---- |__________|
- | | |
- | | |
- G3 |------------G5
- | |
- | |
- __________ __________
- | | | |
- | NET #2 | | NET #3 |
- |__________| |__________|
- |
- |
- G6
- |
- |
- __________
- | |
- | NET #27 |
- |__________|
-
-
-
- NOTE: Gateways G1 - G6 are all routing gateways.
-
-
-
-
-
-
- -20-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 8: ROUTING UPDATES BASED ON NEW ROUTING METHOD
- (SEE FIGURE 7 FOR CONFIGURATION)
-
-
- NETWORK DISTANCES/"NEXT" NEIGHBOR ADDRESS(ES)
-
-
-
- STEP SOURCE DEST. 1 2 3 4 10 26 27
-
-
- 1. G1 ALL Distance INF INF INF INF 0 0 INF
- "Next" G1 G1
-
- 2. G2 ALL Distance 0 1 1 2 1 0 2
- "Next" G2 G3 G5 G1 G1 G2 G3
-
- 3. G2 ALL Distance 1 0 1 2 1 0 1
- "Next" G2 G3 G5 G1 G1 G3 G6
- G5 G5
-
- 4. G4 ALL Distance 2 2 1 0 0 1 3
- "Next" G1 G1 G5 G4 G4 G1 G1
- G5 G5 G5 G5
-
- 5. G5(10) ALL Distance 1 1 0 1 0 0 2
- "Next" G2 G3 G5 G4 G5 G5 G3
-
- 6. G5(26) ALL Distance 1 1 0 1 0 0 2
- "Next" G2 G3 G5 G4 G5 G5 G3
-
- 7. G1 ALL Distance 1 1 1 1 0 0 2
- "Next" G2 G3 G5 G4 G1 G1 G3
-
- Assume loss of connectivity by G2 to Net.#1
-
- 8. G2 ALL Distance INF 1 1 2 1 0 2
- "Next" G3 G5 G5 G5 G2 G3
- G1 G1
-
- 9. G1 ALL Distance INF 1 1 1 0 0 2
- "Next" G3 G5 G4 G1 G1 G3
-
-
- NOTE: G5(10) is gateway 5 on network 10. A gateway which is a
- neighbor on two networks is treated as two gateways. Thus
- G5 is identified as G5(10) and G5(26) by Gateway 1.
-
-
- -21-
-
-
-
- IEN 196 11 September 1981
-
-
-
-
- FIGURE 9: ROUTING UPDATES BASED ON IEN # 109 METHOD
- (SEE FIGURE 7 FOR CONFIGURATION)
-
-
-
-
- NETWORK DISTANCES
-
-
- SOURCE DEST. 1 2 3 4 10 26 27
-
-
- G1 ALL INF INF INF INF 0 0 INF
- G2 G1 0 1 1 2 1 0 2
- G1 G2 INF INF INF INF 0 0 INF
- G1 G3 1 2 2 3 0 0 3
- G1 G4 1 2 2 3 0 0 3
- G1 G5(10) 1 2 2 3 0 0 3
- G1 G5(26) 1 2 2 3 0 0 3
- G3 G1 1 0 1 2 INF 0 1
- G1 G2 INF 1 INF INF 0 0 2
- G1 G3 1 INF INF 2 0 0 INF
- G1 G4 1 1 2 2 0 0 2
- G1 G5(10) 1 1 2 2 0 0 2
- G1 G5(26) 1 1 2 2 0 0 2
- G4 G1 INF INF 1 0 0 INF INF
- G1 G2 INF 1 INF 1 0 0 2
- G1 G3 1 INF INF 1 0 0 INF
- G1 G4 1 1 INF INF 0 0 2
- G1 G5(10) 1 1 2 1 0 0 2
- G1 G5(26) 1 1 2 1 0 0 2
- G5(10) G1 1 1 0 1 0 0 2
- G5(26) G1 1 1 0 1 0 0 2
- G1 G2 INF 1 1 1 0 0 2
- G1 G3 1 INF 1 1 0 0 INF
- G1 G4 1 1 1 INF 0 0 2
- G1 G5(10) 1 1 INF 1 0 0 2
- G1 G5(26) 1 1 INF 1 0 0 2
- Assume loss of connectivity by G2 to Net.#1.
- G2 G1 INF 1 1 INF INF 0 2
- G1 G2 7 1 1 1 0 0 2
- G1 G3 INF INF 1 1 0 0 INF
- G1 G4 INF 1 1 INF 0 0 2
- G1 G5(10) INF 1 INF 1 0 0 2
- G1 G5(26) INF 1 INF 1 0 0 2
-
-
- -22-
-
-
-
- IEN 196 11 September 1981
-
-
- However, in this case, G3 has two paths of distance 1 through
- which it can reach Net.#10. G3 can go through G1 to reach
- Net.#10 in 1 hop or it can go through G5. Since both paths are
- equal and minimum distance, both are reported in the routing
- update.
-
- When routing updates are constructed to include both distance and
- connectivity information as described above, gateways receive
- enough information to perform path checks. This capability
- enables gateways to avoid shuttling problems.
-
- The performance of path checks is illustrated in Figure 7. In
- Figure 8, step 8, G2 sends a routing update which shows that G2
- has lost connectivity to Net.#1 (i.e., distance =inf.). G1 then
- recomputes its minimum distance and routing with respect to
- Net.#1. In these calculations G1 wants to find the shortest path
- but also wants to ensure that it is a "true" path. Therefore, G1
- looks at the first path of distance 1. This path is provided by
- G3. However, G3's "next" neighbor address on this path is G2.
- G2 now shows a path of infinity to Net.#1, so G1 rejects the G3
- route. In examining the other routes of distance 1 (i.e., G5(10)
- and G5(26)), G1 finds that they all go through G2 which G1 knows
- is disconnected. Thus, all the paths of distance 1 are rejected.
-
- Next, G1 looks at the route of distance 2 provided by G4. G4
- shows two "next" addresses, G1 and G5, G1 rejects the path
- through "next" address G1 since this path would obviously result
- in shuttling. G1 then traces the route through "next" address
- G5. Looking at the routing update provided by G5, G1 sees that
- G5 intends to route traffic addressed to Net.#1 through G2. G2
- has already been identified as a dead-end. As G1 has examined
- all known routes to Net.#1 and found no acceptable route, G1
- determines that it is infinity distance to Net.#1 and sends a
- routing update to all its neighbors showing infinity distance to
- Net.#1 (step 9).
-
- The rules involved in the routing scheme described in the example
- plus a few additional rules of the proposed routing scheme are
- defined as follows:
-
- A. On transmission of routing updates, the gateway reports its
- actual distance (minimum distance vector) from each
- network. In addition, for each network, the gateway
- reports the "next" gateway address through which it will
- route any packets addressed to the network. If more than
- one path of the same minimum distance exists, the gateway
- will report all possible "next" gateway addresses
- associated with that network. In IEN # 109 terminology,
- then, each gateway exchanges its "minimum distance vector"
- and its "routing table (list of neighbor gateways through
- which to send traffic to each network)."
-
- -23-
-
-
-
- IEN 196 11 September 1981
-
-
- B. On transmission of routing updates, the gateway sets a
- timer The transmitting gateway does not recompute its
- minimum distance vector or send any new routing updates
- prior to timer expiration.
-
- C. Gateways calculate their routing updates and routing tables
- on the basis of the minimum distance rule. Having selected
- the minimum distance path to a network, the gateway checks
- the "next" gateway address.
-
- 1. If the "next" gateway address is this gateway this
- path is considered unacceptable and the next
- candidate path is checked.
-
- 2. If the "next" gateway address is other than this
- gateway, use the information in the routing update
- matrix to determine if this path (distance of 1 or
- greater) is through a gateway which has reported
- "infinite" distance to the network in question. If
- any step of the path is through a gateway showing
- "infinite" distance to the network, the path is
- considered unacceptable and the next candidate path
- is checked.
-
- Figure 8 shows the routing updates transmitted for the
- configuration shown in Figure 7 when routing is performed IAW IEN
- # 109. Figure 8 shows the routing updates transmitted for the
- same configuration (Figure 7) when the proposed routing scheme is
- used. Both examples are worked from the perspective of G1.
-
- The examples show the differences in the routing updates
- generated under each rule. In both cases, packets would be
- routed correctly. In the proposed routing scheme (see Figure 8),
- fewer routing updates are transmitted with the same results
- obtained. This reduced traffic is due, in part, to the rule
- requiring the gateway to observe a time-delay between
- transmission of routing packets. This rule is particularly
- useful when bringing a gateway on-line because it allows the
- gateway to receive updates from all or almost all of its
- neighbors before responding with its next updates. In addition,
- the gateway is able to respond to the loss of connectivity to
- Net.#1 correctly based on the update input from G2 (see Figure 8)
- following the new method whereas, following the old rules (see
- Figure 9), G1 must receive updates from all neighbors before
- correctly determining that it has no path to Net.#1.
-
-
- -24-
-
-
-
- IEN 196 11 September 1981
-
-
- Under the proposed method, the gateway has a more complex
- algorithm to calculate its routing table. However, once
- calculated, the gateway does not need to "tailor" the updates to
- each neighbor but sends the same information to all neighbors.
- Also, the gateway does not maintain a copy of the last update
- transmitted to determine whether there is new information to be
- transmitted since it transmits updates only when its routing
- table changes. Under IEN # 109, the gateway is required to
- maintain copies of each update last sent to each neighbor and
- compose the new "tailored" updates on an individual basis to
- those last sent.
-
- Finally, the proposed routing method can be correctly implemented
- without requiring any special rules regarding treatment of
- non-routing neighbors. The path checks built into the new
- routing scheme preclude the shuttling problems described above
- which could have occured if non-routing gateways were not treated
- as exceptions.
-
-
-
-
-
-
-
-
- References
-
- 1) V. Strazisar, "Gateway Dynamic Routting", IEN # 25, Bolt,
- Beranek and Newman, January 25, 1978.
-
- 2) V. Strazisar, R. Perlman, "Gateway Routing, An
- Implementation Specification", IEN # 30, April 11, 1978.
-
- 3) V. Strazisar, "How to Build a Gateway", IEN # 109, August
- 31, 1979.
-
-
-
-
-
-
-
-
-
-
-
-
-
- -25-
-
-
-